1. Field of the Invention
The present invention relates to a method and an apparatus for encoding and decoding key data, and more particularly, to an apparatus and a method for encoding key data which are capable of increasing the efficiency of encoding key data by generating differential data performing differential pulse code modulation (DPCM) on key data and by decreasing the range of the differential data to be encoded performing predetermined operations, and to an apparatus and a method for decoding encoded key data.
2. Description of the Related Art
Three-dimensional (3D) representation has been widely used for 3D computer games or a virtual reality environment in a computer system. A virtual reality modeling language (VRML) is used to represent 3D animation.
VRML and MPEG-4 binary format for scene (BIFS) provide an animation representation method based on key framing. In the animation representation method, predetermined key frames are arranged on an arbitrary time axis, and animation data between the key frames are filled by linear interpolation. The key frames are defined by interpolator nodes, and each of the interpolator node is represented by a floating-point number within a predetermined range, for example, a range from −∞ to +∞. Each of the interpolator nodes constitutes fields each consisting of key data representing the position of a certain key frame on the time axis and key value data representing the characteristics and movement information on the key data corresponding to the key data.
In order to represent animation as naturally and smoothly as the movement of a real object by using key framing, which is a piecewise linear interpolation, a considerable amount of key frame information must be provided via each of the interpolator nodes, the fact which causes serious problems in terms of computational costs and efficiency. In the event where key framing is used in an off-line circumstance, a storage of a large capacity is needed to store a considerable amount of 3D animation data. In addition, when used in an on-line circumstance, key framing also requires not only such a large capacity storage but also high-speed data transmission lines, which can transmit a considerable amount of data at a time at high speeds, so as to transmit 3D animation information from a server to a terminal. In this case, as the possibility of errors to occur during transmission of data increases, the reliability of the data decreases. Therefore, an effective method for compressing and decoding data so as to reduce the amount of interpolator node data is required.
MPEG-4 BIFS provides two different methods for encoding animation data. One is BIFS-Q for encoding animation data, and the other is differential pulse code modulation (DPCM) for encoding differences among data. DPCM is also called predictive MF coding (PMFC). BIFS-Q only uses quantization and thus is not considered effective. PMFC is considered more effective than BIFS-Q because in PMFC, entropy encoding is performed to remove redundant data after DPCM is performed. A PMFC encoder and a PMFC decoder for key data is shown in FIG. 1. As described above, PMFC is not sufficiently effective in encoding animation data because it only performs DPCM before entropy encoding without taking into consideration the characteristics of keys and a correlation between the keys.
Referring to FIG. 1, input key data 105 is input into an encoder 100. A quantizer 110 receives the input key data 105 and quantizes them into integers. A DPCM processor 115 receives the quantized key data and generates differential data. An entropy encoder 120 receives the differential data, removes redundancy existing among bits in terms of the probability of symbols occurring, and generates a compressed bitstream 125. The bitstream 125 generated by the encoder 100 shown in FIG. 1 is input into an entropy decoder 155 of a decoder 150 and is entropy-decoded. The entropy-decoded differential data are input into an inverse DPCM processor 160 as quantized differential data, and an inverse quantizer 165 performs inverse quantization on the quantized key data input from the inverse DPCM processor 160 and outputs decoded key data.
However, the encoder 100 only performs DPCM before entropy encoding without considering the characteristics of a key, and thus it is very difficult to achieve effective encoding showing a high compression rate.